/* 矩阵乘法+快速幂+背景(多为DP，递推)
* 1.矩阵乘法
    A·B * B·I = A·C
     p  *  Q  =  R
    a中不能有变量

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= c; j++)
            for(int k = 1; k <= B; k++)
                R[i][j] += P[i][k] * Q[k][j];

* 本题:
    P[n] = n*S[n] - T[n] = (n-1)F1 + (n-2)F2 + ... + F[n-1]
    P[n+1] = (n+1)S[n+1] - T[n+1]
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long

const int N = 4;
int n, m; 

void mul(int c[][N], int a[][N], int b[][N])
{
    static int temp[N][N]; //static提高效率，只初始化一次，不用重复开辟空间
    memset(temp, 0, sizeof temp);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                temp[i][j] = (temp[i][j] + 1ll*a[i][k]*b[k][j]) % m;

    memcpy(c, temp, sizeof temp);

}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> m;

    int f1[N][N] {1, 1, 1, 0};
    int a[N][N] ={
        {0, 1, 0, 0},
        {1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 0, 0, 1}
    };

    int k = n-1;
    //快速幂
    while(k)
    {
        if(k&1) mul(f1, f1, a); // f1 = f1 * a -> res = res * a
        mul(a, a, a); // a = a * a -> base = base * base
        k >>= 1;
    }
    cout << ((n*f1[0][2] - f1[0][3])%m + m) %m << endl;
    return 0;
}
